1. Field of the Invention
The field of the invention is data processing, or, more specifically, methods, systems, and products for memory mapping to reduce cache conflicts in multiprocessor systems.
2. Description of Related Art
Many computer systems employ a multilevel hierarchy of memory systems, with fast but limited capacity memory at the highest level of the hierarchy and proceeding to slower but higher capacity memory at the lowest level of the hierarchy. Such a memory hierarchy typically includes a small fast memory called a cache, either physically integrated within a processor integrated circuit or mounted physically close to the processor for speed. There may be multiple levels of caches, often referred to as Level 1 or L1, Level 2 or L2, and so on.
A memory hierarchy is useful only if a high percentage of items requested from memory are present in the highest levels of the hierarchy when requested. If a processor requests an item from a cache and the item is present in the cache, the event is called a cache hit. If a processor requests an item from a cache and the item is not present in the cache, the event is called a cache miss. In the event of a cache miss, the requested item is retrieved from a lower level of the memory hierarchy. Cache misses have a significant impact on performance. In general, minimization of cache misses and minimization of the effects of cache misses are some of the most important design parameters for overall computer system performance.
The minimum amount of memory that can be transferred between a cache and a next lower level of the memory hierarchy is called a “line,” or sometimes a “block.” A real memory is typically organized in bytes of eight bits, or in words (for example, 32 bits per word), and a cache line is typically multiple words (for example, 16 words per line). Memory typically also is organized into pages, with multiple lines per page.
If a cache stores an entire line address along with the data, any line can be placed anywhere in the cache. A space saving alternative is to organize a cache with a subset of a memory address, called an index. In a cache with indexing, an item with a particular real memory address can be placed in the cache only at the one place within the cache designated by the index. In addition, every item within the address space having identical index bits will potentially require the same line space within the cache. A new line may be fetched that requires the same space in the cache as an existing line and the existing line may need to stay in the cache. This condition is called a conflict, and is discussed in more detail below.
If a line can appear at only one place in the cache, the cache is said to be direct mapped (and is said to have low associativity). In an alternative design, a cache may be organized into sets, each set containing two or more lines. If a line can be placed in only one of the sets, the cache is said to be set associative. If a line can be placed anywhere in the cache, the cache is said to be fully associative. In general, caches having low associativity are simpler, faster and require less space than caches having high associativity. Direct mapped or other low associativity caches may have performance problems, however, due to conflicts as discussed below.
For a direct mapped cache or other low associativity cache, a new line may require the same space as an existing line. That is, instead of displacing lines randomly, or displacing the least recently used line, the new line displaces the line having the same index within the cache. The displaced line may be useful and may need to stay in the cache. A miss resulting from a useful line being displaced by a line having the same index is called a conflict miss. In executing some software, a second line may displace a first line, only to have the first line soon displace the second line. This thrashing of a single cache line can result in low system performance, even though the cache size is adequate for the particular software.
Destructive cache interference from conflict misses can occur in any environment that supports multiprocessing, where different execution contexts operate in a time-shared manner on the same physical processor and share the same cache hierarchy. Examples of such multiprocessing environments include simultaneous multithreading (“SMT”) environments and shared processor logical partitioning (“SPLPAR”) environment. In fact, SMT and SPLPAR particularly exacerbate destructive cache interference. In the case of SMT, interleaving of different contexts of execution is carried out a very fine granularity, often within a dispatch cycle, resulting in increased cache interference. In the case of SPLPAR, a single physical processor and its associated cache hierarchy is shared by multiple operating system images, with no data shared between the different operating system images. In SPLPAR environments, therefore, all cache sharing results in destructive interference.
There is an ongoing need to improve system ability to provide the speed and space advantages of low associativity caches while minimizing the negative effects on system performance due to conflict misses. One approach to reducing the impact of conflict misses in direct mapped caches, for example, is to add a small fully associative secondary cache. This approach may include loading the small secondary cache with the displaced victim of a miss, calling the resulting secondary cache a victim cache.
Software approaches for reducing conflict misses include page mapping techniques such as page coloring and bin hopping. While these techniques have been shown to reduce cache conflicts when a physical cache is shared by different threads of execution belonging to the same operating system image, they do not address the case where different operating system images may share the same physical cache. There is a further ongoing need therefore for improvement in operating system policies in multiprocessor systems in which multiple operating system images use the same physical cache.